package com.xieyong.leetcode;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class Leetcode2434 {
    public static void main(String[] args) {

        Leetcode2434 leetcode = new Leetcode2434();
        String s = "bdda";
        String s1 = leetcode.robotWithString(s);
        System.out.println(s1);
    }

    public String robotWithString(String s) {

        StringBuilder res = new StringBuilder();
        Map<Character, Integer> map = new HashMap<>();
        Stack<Character> stack = new Stack<>();
        for (Character c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        char minchar = 'a';
        for (char c : s.toCharArray()) {
            stack.push(c);
            map.put(c, map.get(c) - 1);
            while (minchar != 'z' && (!map.containsKey(minchar) || map.get(minchar) == 0)) {
                minchar++;
            }
            while (!stack.isEmpty() && stack.peek() <= minchar) {
                res.append(stack.pop());
            }
        }
        return res.toString();
    }
}

//        Stack<Character> stack = new Stack<>();
//        StringBuilder res = new StringBuilder();
//        int index = 0;
//        for (int i = 0; i < 26; i++) {
//            char c = (char) ('a' + i);
//            int lastIndex = s.lastIndexOf(c);
//            if (lastIndex != -1) {
//                if (lastIndex < index) {
//                    StringBuilder temp = new StringBuilder();
//                    while (!stack.isEmpty()) {
//                        temp.append(stack.pop());
//                    }
//                    res.append(temp);
//                }
//                for (int j = index; j <= lastIndex; j++) {
//                    if (s.charAt(j) == c) {
//                        res.append(s.charAt(j));
//                    } else {
//                        stack.push(s.charAt(j));
//                    }
//                }
//                index = lastIndex + 1;
//            }
//        }
//        return res.toString();


//        if (s == null || s.isEmpty()) {
//            return "";
//        }
//        int lastindex = -1;
//        StringBuilder res = new StringBuilder();
//        Map<Character, Integer> map = new HashMap<>();
//        for (Character c : s.toCharArray()) {
//            map.put(c, map.getOrDefault(c, 0) + 1);
//        }
//        for (int i = 0; i < 26; i++) {
//            char c = (char)('a' + i);
//            lastindex = s.lastIndexOf(c);
//
//            if (lastindex != -1) {
//                if (map.get(c) == 1) {
//                    res.append(c);
//                    res.append(robotWithString(s.replace(s.substring(lastindex,lastindex + 1), "")));
//                } else {
//                    StringBuilder sb = new StringBuilder();
//                    for (int j = 0; j <= lastindex; j++) {
//                        if(s.charAt(j) == 'a' + i) {
//                            res.append(s.charAt(j));
//                        } else {
//                            sb.append(s.charAt(j));
//                        }
//                    }
//                    res.append(sb.reverse());
//                    res.append(robotWithString(s.substring(lastindex + 1)));
//
//                }
//                break;
//            }
//        }
//        return res.toString();
//    }
//}
